/**
 * describe:
 *
 * @author chaP
 * @date 2019/03/19
 */
package CodingTest.AC20190317;
/**
 * 全排序：
 * 给定一个没有重复数字的序列，返回其所有可能的全排列。

 示例:

 输入: [1,2,3]
 输出:
 [
 [1,2,3],
 [1,3,2],
 [2,1,3],
 [2,3,1],
 [3,1,2],
 [3,2,1]
 ]
 */

import java.util.ArrayList;
import java.util.List;

public class AllSort {
    public List<List<Integer>> perm(int[] nums){
        List<List<Integer>> res = new ArrayList<>();
        dfs(res,nums,0);
        return res;
    }
    public void dfs(List<List<Integer>> res,int[] nums,int from){
        if(from == nums.length){
            List<Integer> tmp = new ArrayList();
            for(int i = 0;i<nums.length;i++){
                tmp.add(nums[i]);
            }
            res.add(tmp);
        }else{
            for(int j = from;j<nums.length;j++){
                swap(nums,from,j);
                dfs(res,nums,from+1);
                swap(nums,j,from);
            }
        }
    }
    public void swap(int[] nums,int i,int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

}
